package leetcode.array;

/**
 * @author Cheng Jun
 * @version 1.0 @Description: 快速排序的通用解法，因为 leetcode.array.sortArray 中的快排方法写得复杂，故重新学习一下
 *     https://leetcode.cn/problems/sort-an-array/
 * @date 2022/7/19 9:32
 * @see sortArray
 */
public class sortArray1 {

  public static void main(String[] args) {
    sortArray(new int[] {5, 2, 3, 1});
  }

  static int[] sortArray(int[] nums) {
    int n = nums.length;
    quickSort(nums, 0, n - 1);
    return nums;
  }

  static void quickSort(int[] nums, int start, int end) {
    if (start >= end) {
      return;
    }
    // 此处交换是为让 pivot 更具有区分度，因为通过 quickSort 后，nums[start] 往往在 nums[start]~nums[end]最小。
    // 通常这里也可以使用 Random 随机确定一个下标，与 nums[start] 进行交换。
    // int randomIndex = new Random().nextInt(end - start + 1) + start;
    // swap(nums, start, randomIndex);
    swap(nums, start, (start + end) / 2);
    int pivot = nums[start];
    int left = start;
    int right = end;
    // [2, 1, 3]
    // 尝试找到两个数 numLeft，numRight，其中numLeft > pivot, numRight <= pivot，找到后就交互位置
    while (left < right) {
      // 从右边开始找，找到第一个小于等于 pivot 的数，因为nums[left]就是pivot，所以right--，不会越界
      while (pivot < nums[right]) {
        right--;
      }
      // 从左边开始找，找到第一个大于 pivot 的数，因为 right会变化，所以要保证left < right
      while (left < right && nums[left] <= pivot) {
        left++;
      }
      // 如果 left 不等于 right，就交换位置
      // if (left != right) swap(nums, left, right);
      // 可以直接交换，只是可能多几次原地交换，但更好理解
      swap(nums, left, right);
    }
    // 最后要交换 pivot 和 nums[right]，即最后一个小于等于pivot的数字放到pivot的左边，
    // 这样pivot的左边数字都小于等于pivot，pivot右边数字都大于pivot
    swap(nums, start, right);
    quickSort(nums, start, right - 1);
    quickSort(nums, right + 1, end);
  }

  static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

}
